package il.ac.bgu.cs.heuristics.utils;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 
 * @author Ronen Pinko
 * 
 */
public final class MathUtils{
	private MathUtils() {
	} // no instantiation

	static <E> Set<List<E>> createPermutations(List<E> elements) {
		Validation.ensureArgumentNeverNull(elements);
		if (elements.isEmpty()) {
			final Set<List<E>> empty = CollectionUtils.newLinkedHashSet();
			empty.add(new ArrayList<E>());
			return empty;
		}
		final Set<List<E>> permutations = CollectionUtils.newLinkedHashSet();
		for (E e : elements) {
			final ArrayList<E> copy = CollectionUtils.newArrayList(elements);
			copy.remove(e);
			for (List<E> permutation : createPermutations(copy)) {
				permutation.add(0, e);
				permutations.add(permutation);
			}
		}
		return permutations;
	}

	public static int average(int i, int j) {
		return (int) (((long) i + j) / 2);
	}

	static <E> Set<Set<E>> createKCombinations(Set<E> elements, int k) {
		Validation.ensureArgumentNeverNull(elements);
		if (elements.size() < k) {
			throw new IllegalArgumentException(
			        "elements size must be at least k");
		}
		if (k == 0) {
			final Set<Set<E>> empty = CollectionUtils.newLinkedHashSet();
			empty.add(CollectionUtils.<E> newLinkedHashSet());
			return empty;
		}
		final Set<Set<E>> combinations = CollectionUtils.newLinkedHashSet();
		for (E e : elements) {
			final Set<E> copy = CollectionUtils.newLinkedHashSet(elements);
			copy.remove(e);
			for (Set<E> combination : createKCombinations(copy, k - 1)) {
				combination.add(e);
				combinations.add(combination);
			}
		}
		return combinations;
	}

	static <E> Set<List<E>> createKPermutations(Set<E> elements, int k) {
		final Set<List<E>> kPermutations = CollectionUtils.newLinkedHashSet();
		final Set<Set<E>> kCombinations = createKCombinations(elements, k);
		for (Set<E> combination : kCombinations) {
			kPermutations.addAll(createPermutations(new ArrayList<E>(
			        combination)));
		}
		return kPermutations;
	}

	/**
	 * Caches results for permutation operations
	 * 
	 * @author Ronen Pinko
	 * 
	 * @param <E>
	 *            type of operations
	 */
	public static final class PermutationResultCache<E> {
		private final Map<Integer, Set<Set<E>>> combinationCache = CollectionUtils
		        .newHashMap();
		private final Map<Integer, Set<List<E>>> permutationCache = CollectionUtils
		        .newHashMap();

		public Set<List<E>> createKPermutations(Set<E> elements, int k) {
			Set<List<E>> kPermutations = permutationCache.get(k);
			if (kPermutations == null) {
				if (elements.size() == k) {
					return createPermutations(new ArrayList<E>(elements));
				} else {
					Set<Set<E>> kCombinations = combinationCache.get(k);
					if (kCombinations == null) {
						kCombinations = createKCombinations(elements, k);
						combinationCache.put(k, kCombinations);
					}
					kPermutations = CollectionUtils.newLinkedHashSet();
					for (Set<E> kCombination : kCombinations) {
						kPermutations
						        .addAll(createPermutations(new ArrayList<E>(
						                kCombination)));
					}
					permutationCache.put(k, kPermutations);
					return kPermutations;
				}
			} else {
				return kPermutations;
			}

		}

	}

}
